package com.zp.self.module.编程测试.tree;

import org.junit.Test;

import java.util.*;

/**
 * @author By ZengPeng
 * @Description
 *            a
 *         /  \
 *       b    c
 *      / \     \
 *     e  f     d
 *          \
 *           g
 *
 * closestparent(e, f) = b
 * closestparent(f, d) = a
 * closestparent(g, b) = b
 *
 * @date in  2021/4/9 16:53
 * @Modified By
 */
public class 二叉树找最近父节点_2021_4_9 {
    static Tree a = new Tree().setValue("a");

    @Test
    public void test2() {

        Tree b = new Tree().setValue("b");
        Tree c = new Tree().setValue("c");
        Tree d = new Tree().setValue("d");
        Tree e = new Tree().setValue("e");
        Tree f = new Tree().setValue("f");
        Tree g = new Tree().setValue("g");

        a.left = b;
        a.right = c;
        b.left = e;
        b.right = f;
        c.right = d;
        f.right = g;

        System.out.println(getCommonParent("e", "f"));
        System.out.println(getCommonParent("f", "d"));
        System.out.println(getCommonParent("g", "b"));
    }

    private String getCommonParent(String e, String f) {
        //1.获取映射关系
        Map<String, String> map = new HashMap<>();
        if (a != null){
            getChildAndParent(a, map);
        }
        //2.获取第一个节点的祖宗集合
        List<String> parents = new ArrayList<>();
        parents.add(e);
        while (map.containsKey(e)){
            parents.add(map.get(e));
            e = map.get(e);
        }

        //3.获取第二个几点的祖宗集合，并判断是否存在于，当前list中
        while (map.containsKey(f)){
            if(parents.contains(f))
                return f;
            f = map.get(f);
        }

        return a.value;
    }

    private void getChildAndParent(Tree parent, Map<String, String> map) {
        if (parent.left != null) {
            map.put(parent.left.value, parent.value);
            getChildAndParent(parent.left, map);
        }
        if (parent.right != null) {
            map.put(parent.right.value, parent.value);
            getChildAndParent(parent.right, map);
        }
    }
}
